CF 350B

题目内容

题目链接

给定一张 $n$ 个节点的有向图，部分节点有标记。每个节点 $i$（$1\le i\le n$）至多只可能被一个节点 $a_i$ 邻接，且有标记节点不可能邻接任何节点。试找出该图中的一个最长通路 $P=⟨p_1,p_2,\cdots ,p_n⟩$，满足：

1. $p_1,p_2,\cdots ,p_{n-1}$ 无标记，但 $p_n$ 有标记。
2. 对于任意的节点 $p_i$，其出度至多为 $1$。

解法

AC 代码

见提交记录。